package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 * [[1,2,3],
 * [4,5,6],
 * [7,8,9]]
 * 输出：[1,2,4,7,5,3,6,8,9]
 * https://leetcode.cn/leetbook/read/array-and-string/cuxq3/
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 104
 * 1 <= m * n <= 104
 * -10^5 <= mat[i][j] <= 10^5
 * @version 1.0
 * @date 2023/9/17 20:47
 */
public class findDiagonalOrder {


    public static void main(String[] args) {
        int[][] matrix = {
                new int[]{1, 2, 3},
                new int[]{4, 5, 6,},
                new int[]{7, 8, 9}

        };
        findDiagonalOrder(matrix);
    }

    // [a(0,0), a(0,1),...    a(0,n-2),    a(0,n-1)]
    // [a(1,0), a(1,1),...    a(1,n-2),    a(1,n-1)]
    // .
    // .
    // .
    // [a(n-2,0), a(n-2,1),...a(n-2,n-2),a(n-2,n-1)]
    // [a(n-1,0), a(n-1,1),...a(n-1,n-2),a(n-1,n-1)]
    public static int[] findDiagonalOrder(int[][] mat) {
        int i = 0;
        int j = 0;
        int counter = 0;
        int row = mat.length;
        int col = mat[0].length;
        int total = row * col;
        int[] resArr = new int[total];
        // 方向是否向上
        boolean up = true;
        while (counter < total) {
            resArr[counter++] = mat[i][j];
            if (up) {
                // 向上越界 行越界
                if (--i < 0) {
                    i = 0;
                    // 向右越界 列越界
                    if (++j == col) {
                        i++;
                        j--;
                    }
                    up = false;
                } else {
                    // 向右越界 列越界
                    if (++j == col) {
                        i += 2;
                        j--;
                        up = false;
                    }
                }
            } else {
                // 向下越界 行越界
                if (++i == row) {
                    i = row - 1;
                    // 向左越界 列越界
                    // if (--j < 0) {
                        j += 2;
                    // }
                    up = true;
                } else {
                    // 向左越界 列越界
                    if (--j < 0) {
                        j++;
                        up = true;
                    }
                }

            }
        }
        return resArr;
    }
}


